// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;
import java.util.Arrays;



class StateIdSetList implements Cloneable {
  public StateIdSetList clone() {
    try {
      // TODO: возмонжо, через new + copyTo быстрее.
      final StateIdSetList result = (StateIdSetList)super.clone();
      fullCopyTo(result);
      return result;
    } catch(CloneNotSupportedException e) {
      assert false;
      return null;
    }
  }

  StateIdSetList(final int length) {
    dense_ = new int[length];
    sparse_ = new int[length];
    clear();
  }

  int[] dense() {
    return dense_;
  }
  int[] sparse() {
    return sparse_;
  }

  void copyTo(final StateIdSetList rhv) {
    if ( rhv.capacity() != capacity() ) {  // никогда не должно выполняться
      fullCopyTo(rhv);
      return;
    }

    rhv.clear();
    for ( int i = 0 ; i != size_ ; i++ ) {
      rhv.pushNew(dense_[i]);
    }
  }


  boolean contains(final int value) {
    return value < capacity() &&
           sparse_[value] < size_ &&
           dense_[sparse_[value]] == value;
  }

  boolean push(final int value) {
    if ( contains(value) ) { return false; }
    pushNew(value);
    return true;
  }
  void pushNew(final int value) {
    assert !contains(value);
    sparse_[value] = size_;
    dense_[size_++] = value;
  }

  int top() {
    assert !isEmpty();
    return dense_[size_ - 1];
  }
  int pop() {
    assert !isEmpty();
    return dense_[--size_];
  }

  void clear() {
    size_ = 0;
  }

  boolean isEmpty() {
    return size_ == 0;
  }
  int size() {
    return size_;
  }
  int capacity() {
    return sparse_.length;
  }

  // Обмен полей двух объектов. Аналогично C++.
  void swap(final StateIdSetList rhv) {
    final int[] tmp_dense = rhv.dense_;
    rhv.dense_ = dense_;
    dense_ = tmp_dense;

    final int[] tmp_sparse = rhv.sparse_;
    rhv.sparse_ = sparse_;
    sparse_ = tmp_sparse;

    final int tmp_size = rhv.size_;
    rhv.size_ = size_;
    size_ = tmp_size;
  }


  private void fullCopyTo(final StateIdSetList rhv) {
    rhv.dense_ = Arrays.copyOf(dense_, dense_.length);
    rhv.sparse_ = Arrays.copyOf(sparse_, sparse_.length);
    rhv.size_ = size_;
  }

  private int[] dense_;   // список
  private int[] sparse_;  // множество
  private int size_;
}
